package Q3;

import java.util.ArrayList;

public class Solution {

    public int n;
    public char[] ch;
    public ArrayList<String> list = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here

        n = str.length();
        ch = str.toCharArray();

        dfs(new StringBuilder(), new boolean[n]);

        return list;
    }

    public void dfs(StringBuilder stringBuilder, boolean[] flag) {
        if (stringBuilder.length() == n) {
            list.add(stringBuilder.toString());
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!flag[i]) {
                flag[i] = true;
                stringBuilder.append(ch[i]);
                dfs(stringBuilder, flag);

                //回溯
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                flag[i] = false;
            }
        }
    }
}